Ćwiczenia/2. Ćwiczenia/Zadanie 3. (szukanie sumy).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Dana jest posortowana tablica A[1...n] oraz liczba x. Proszę napisać program, który stwierdza czy istnieją indeksy i oraz j takie, że A[i] +A[j] = x."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ponieważ wiemy, że sekwencja jest posortowana (jeżeli nie jest powiedziane inaczej, zakładamy, że jest to porządek niemalejący), możemy przeszukać tablicę w czasie liniowym. Wynika to stąd, że poruszając się wskaźnikiem od lewej storny sekwencji, w każdym następnym kroku przemieszczamy się na element taki sam lub większy, natomiast przesuwając się wskażnikiem od prawej strony, w każdym następnym kroku przemieszczamy się na element o wartości takiej samej lub mniejszej niż poprzedni. Łatwo można zauważyć, że jeżeli dla bieżącego ułożenia wskażników i oraz j suma jest za mała, musimy zwiększyć sumę, przesuwając wskażnik lewy ($ i $) w prawą stronę. Jeżeli ta suma jest zbyt duża, przesuwamy prawy wskażnik ($ j $) w lewo, aby zmniejszyć sumę."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_indices(arr, target_sum):\n",
    "    i = 0\n",
    "    j = len(arr) - 1\n",
    "    \n",
    "    while i < j:\n",
    "        curr_sum = arr[i] + arr[j]\n",
    "        if curr_sum == target_sum: return i, j\n",
    "        if curr_sum < target_sum: i += 1\n",
    "        else: j -= 1\n",
    "            \n",
    "    return None, None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Przykładowy test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#1 Loop:\n",
      "Values: [-47, -45, -29, -22, -21, -20, -19, -15, -14, -13, -10, -9, -6, 2, 7, 7, 10, 13, 23, 27, 28, 35, 36, 43, 46, 48, 49]\n",
      "Target sum: -3\n",
      "Found indices: i=9 (values[9]=-13), j=16 (values[16]=10)\n",
      "#2 Loop:\n",
      "Values: [-50, -40, -40, -38, -32, -30, -29, -26, -25, -22, -13, -10, -6, -1, 0, 2, 8, 10, 10, 14, 19, 23, 26, 27, 27, 28, 30, 31, 32, 45]\n",
      "Target sum: 73\n",
      "Found indices: i=25 (values[25]=28), j=29 (values[29]=45)\n",
      "#3 Loop:\n",
      "Values: [-40, -34, -32, -27, -17, -13, -7, 3, 5, 11, 17, 18, 30, 41, 47, 47]\n",
      "Target sum: 12\n",
      "Found indices: i=None , j=None \n",
      "#4 Loop:\n",
      "Values: [-43, -41, -38, -37, -36, -29, -29, -28, -26, -21, -16, -10, -9, -9, -6, 1, 10, 11, 12, 22, 22, 25, 25, 30, 31, 34, 47, 50]\n",
      "Target sum: -97\n",
      "Found indices: i=None , j=None \n",
      "#5 Loop:\n",
      "Values: [-49, -47, -46, -46, -43, -41, -40, -34, -34, -29, -26, -23, -21, -13, -10, 5, 10, 11, 13, 16, 21, 22, 24, 33, 36, 36, 40, 41, 46]\n",
      "Target sum: 27\n",
      "Found indices: i=13 (values[13]=-13), j=26 (values[26]=40)\n",
      "#6 Loop:\n",
      "Values: [-41, -22, -12, -10, -9, -8, 7, 17, 24, 28, 29, 32, 41, 42]\n",
      "Target sum: 44\n",
      "Found indices: i=None , j=None \n",
      "#7 Loop:\n",
      "Values: [-49, -43, -35, -31, -28, -27, -26, -25, -24, -22, -22, -16, -11, -3, 3, 6, 17, 18, 28, 39, 39, 40, 42, 43, 45, 50, 50]\n",
      "Target sum: -96\n",
      "Found indices: i=None , j=None \n",
      "#8 Loop:\n",
      "Values: [-12, -12, 3, 3, 8, 10, 16, 16, 34, 40]\n",
      "Target sum: -7\n",
      "Found indices: i=None , j=None \n",
      "#9 Loop:\n",
      "Values: [-49, -48, -45, -35, -32, -30, -22, -19, -12, -5, -4, 16, 19, 20, 22, 26, 38, 48]\n",
      "Target sum: 46\n",
      "Found indices: i=13 (values[13]=20), j=15 (values[15]=26)\n",
      "#10 Loop:\n",
      "Values: [-47, -38, -37, -30, -23, -17, -8, 1, 7, 8, 8, 12, 30, 33, 35, 39, 43]\n",
      "Target sum: -7\n",
      "Found indices: i=2 (values[2]=-37), j=12 (values[12]=30)\n",
      "#11 Loop:\n",
      "Values: [-49, -46, -45, -34, -25, -21, -12, -12, -11, -8, -7, -5, -2, 6, 9, 11, 15, 20, 28, 28, 29, 31, 40, 46, 48]\n",
      "Target sum: -71\n",
      "Found indices: i=1 (values[1]=-46), j=4 (values[4]=-25)\n",
      "#12 Loop:\n",
      "Values: [-48, -40, -36, -33, -31, -30, -29, -25, -24, -20, -18, 12, 21, 22, 23, 24, 28, 30, 39]\n",
      "Target sum: -57\n",
      "Found indices: i=3 (values[3]=-33), j=8 (values[8]=-24)\n",
      "#13 Loop:\n",
      "Values: [-44, -43, -20, 5, 11, 22, 23, 28, 29, 38, 39]\n",
      "Target sum: 97\n",
      "Found indices: i=None , j=None \n",
      "#14 Loop:\n",
      "Values: [-50, -41, -34, -24, -20, -7, -1, 0, 12, 12, 13, 25, 30, 33, 37, 39, 41]\n",
      "Target sum: 40\n",
      "Found indices: i=6 (values[6]=-1), j=16 (values[16]=41)\n",
      "#15 Loop:\n",
      "Values: [-50, -49, -47, -41, -38, -28, -24, -24, -22, 0, 4, 7, 20, 29, 34, 36, 38, 42, 47, 49, 49]\n",
      "Target sum: 72\n",
      "Found indices: i=14 (values[14]=34), j=16 (values[16]=38)\n",
      "#16 Loop:\n",
      "Values: [-49, -45, -41, -32, -31, -25, -22, -20, -16, -10, -7, -7, 8, 11, 12, 16, 18, 21, 21, 24, 26, 26, 31, 31, 31, 34, 35, 43]\n",
      "Target sum: -57\n",
      "Found indices: i=2 (values[2]=-41), j=8 (values[8]=-16)\n",
      "#17 Loop:\n",
      "Values: [-43, -41, -41, -36, -23, -22, -14, -14, -12, -10, -3, -2, 1, 8, 13, 42, 45]\n",
      "Target sum: 86\n",
      "Found indices: i=None , j=None \n",
      "#18 Loop:\n",
      "Values: [-49, -47, -44, -40, -39, -31, -31, -29, -26, -18, -18, -5, -2, -2, 3, 7, 10, 11, 11, 14, 16, 22, 32, 36, 37, 38, 39, 40]\n",
      "Target sum: 95\n",
      "Found indices: i=None , j=None \n",
      "#19 Loop:\n",
      "Values: [-48, -46, -45, -43, -30, -27, -23, -11, -6, -5, -5, -4, -3, 0, 1, 2, 7, 18, 21, 33, 43, 46, 46, 46, 47]\n",
      "Target sum: 77\n",
      "Found indices: i=None , j=None \n",
      "#20 Loop:\n",
      "Values: [-49, -39, -31, -27, -26, -15, -4, 12, 19, 30, 43]\n",
      "Target sum: -69\n",
      "Found indices: i=None , j=None \n",
      "#21 Loop:\n",
      "Values: [-34, -33, -30, -29, -28, -27, -20, -17, -16, -11, -11, -11, -6, -5, -4, -2, 8, 11, 13, 18, 22, 26, 28, 31, 37, 39, 40, 42, 42]\n",
      "Target sum: 98\n",
      "Found indices: i=None , j=None \n",
      "#22 Loop:\n",
      "Values: [-40, -37, -36, -30, -21, -21, 10, 16, 25, 35]\n",
      "Target sum: -68\n",
      "Found indices: i=None , j=None \n",
      "#23 Loop:\n",
      "Values: [-43, -42, -41, -41, -32, -23, -21, -20, -20, -19, -11, -10, -8, 0, 8, 25, 26, 32, 40, 43, 45]\n",
      "Target sum: -28\n",
      "Found indices: i=7 (values[7]=-20), j=12 (values[12]=-8)\n",
      "#24 Loop:\n",
      "Values: [-49, -37, -24, -20, -15, -10, -8, -8, 6, 12, 13, 16, 20, 27, 33, 41, 47]\n",
      "Target sum: 76\n",
      "Found indices: i=None , j=None \n",
      "#25 Loop:\n",
      "Values: [-30, -13, -13, -1, 2, 11, 18, 20, 28, 34, 35, 35, 35, 37, 39]\n",
      "Target sum: -70\n",
      "Found indices: i=None , j=None \n",
      "#26 Loop:\n",
      "Values: [-48, -41, -40, -38, -32, -22, -18, -18, -6, -2, 0, 9, 11, 13, 20, 25, 39, 42, 43, 47]\n",
      "Target sum: -77\n",
      "Found indices: i=None , j=None \n",
      "#27 Loop:\n",
      "Values: [-48, -43, -35, -27, -26, -24, -22, -22, -6, -1, -1, 3, 8, 12, 14, 23, 26, 28, 38, 40, 46, 50]\n",
      "Target sum: 3\n",
      "Found indices: i=1 (values[1]=-43), j=20 (values[20]=46)\n",
      "#28 Loop:\n",
      "Values: [-50, -48, -31, -26, -12, -12, 3, 7, 24, 26, 27, 32, 34, 42]\n",
      "Target sum: 70\n",
      "Found indices: i=None , j=None \n",
      "#29 Loop:\n",
      "Values: [-49, -47, -46, -46, -45, -37, -29, -29, -27, -25, -24, -24, -18, -16, -14, -3, 9, 9, 10, 24, 26, 31, 32, 33, 33, 33, 43, 47]\n",
      "Target sum: -16\n",
      "Found indices: i=0 (values[0]=-49), j=25 (values[25]=33)\n",
      "#30 Loop:\n",
      "Values: [-48, -46, -40, -38, -35, -35, -34, -33, -29, -29, -27, -19, -16, -12, -10, 3, 15, 16, 17, 17, 24, 37, 49]\n",
      "Target sum: 69\n",
      "Found indices: i=None , j=None \n",
      "#31 Loop:\n",
      "Values: [-26, -12, -11, -11, -10, -6, 19, 27, 29, 30, 41, 49]\n",
      "Target sum: 34\n",
      "Found indices: i=None , j=None \n",
      "#32 Loop:\n",
      "Values: [-47, -39, -35, -35, -22, -20, -17, -17, -15, -2, 5, 10, 16, 16, 18, 34, 35, 46]\n",
      "Target sum: -36\n",
      "Found indices: i=None , j=None \n",
      "#33 Loop:\n",
      "Values: [-50, -47, -46, -40, -36, -35, -33, -18, -17, -15, -8, -8, -8, 4, 7, 11, 14, 19, 22, 29, 32, 37, 39, 41, 44, 45, 48, 49]\n",
      "Target sum: 35\n",
      "Found indices: i=None , j=None \n",
      "#34 Loop:\n",
      "Values: [-43, -39, -34, -22, -10, -10, -10, -5, -4, 6, 9, 9, 14, 17, 19, 26, 34, 36, 42]\n",
      "Target sum: 13\n",
      "Found indices: i=8 (values[8]=-4), j=13 (values[13]=17)\n",
      "#35 Loop:\n",
      "Values: [-50, -50, -47, -40, -35, -20, -15, -10, -10, -2, -2, 10, 25, 26, 30, 34, 37, 43, 44]\n",
      "Target sum: -6\n",
      "Found indices: i=0 (values[0]=-50), j=18 (values[18]=44)\n",
      "#36 Loop:\n",
      "Values: [-39, -39, -26, -11, -3, 0, 5, 16, 33, 42, 47, 48]\n",
      "Target sum: 10\n",
      "Found indices: i=None , j=None \n",
      "#37 Loop:\n",
      "Values: [-37, -32, -30, -29, -23, -11, -8, 0, 2, 10, 12, 17, 21, 29, 30, 36, 40, 40, 46, 47]\n",
      "Target sum: -51\n",
      "Found indices: i=None , j=None \n",
      "#38 Loop:\n",
      "Values: [-45, -39, -34, -33, -28, -27, -6, 2, 10, 14, 19, 20, 27, 34, 41, 41, 42, 44, 49, 50]\n",
      "Target sum: -59\n",
      "Found indices: i=None , j=None \n",
      "#39 Loop:\n",
      "Values: [-50, -29, -21, -15, -14, 6, 28, 36, 46, 49]\n",
      "Target sum: -42\n",
      "Found indices: i=None , j=None \n",
      "#40 Loop:\n",
      "Values: [-49, -42, -37, -35, -33, -26, -24, -24, -15, -9, -7, -4, 1, 1, 8, 21, 24, 25, 27, 28, 30, 32, 34, 36, 44, 46, 46, 50]\n",
      "Target sum: -91\n",
      "Found indices: i=0 (values[0]=-49), j=1 (values[1]=-42)\n",
      "#41 Loop:\n",
      "Values: [-47, -46, -37, -31, -27, -26, -24, -20, -13, -12, -10, -7, -5, 3, 7, 13, 16, 19, 20, 22, 25, 30, 36, 38, 39, 42, 45, 50]\n",
      "Target sum: -22\n",
      "Found indices: i=0 (values[0]=-47), j=20 (values[20]=25)\n",
      "#42 Loop:\n",
      "Values: [-48, -42, -41, -34, -33, -31, -28, -25, -24, -17, -15, -10, -8, -6, 2, 5, 10, 19, 32, 38, 46, 47]\n",
      "Target sum: -29\n",
      "Found indices: i=0 (values[0]=-48), j=17 (values[17]=19)\n",
      "#43 Loop:\n",
      "Values: [-44, -33, -32, -24, -20, -16, -13, -9, -9, -8, 9, 21, 23, 32, 40, 50]\n",
      "Target sum: -45\n",
      "Found indices: i=2 (values[2]=-32), j=6 (values[6]=-13)\n",
      "#44 Loop:\n",
      "Values: [-43, -37, -33, -27, -25, -24, -19, -14, -11, 6, 6, 6, 9, 11, 16, 20, 21, 22, 22, 22, 32, 33, 33, 38, 39, 40, 47, 47]\n",
      "Target sum: -43\n",
      "Found indices: i=5 (values[5]=-24), j=6 (values[6]=-19)\n",
      "#45 Loop:\n",
      "Values: [-43, -39, -39, -38, -34, -25, -22, -21, -9, 12, 15, 26, 49]\n",
      "Target sum: -28\n",
      "Found indices: i=0 (values[0]=-43), j=10 (values[10]=15)\n",
      "#46 Loop:\n",
      "Values: [-50, -48, -47, -35, -29, -22, -22, -13, -6, -1, 1, 8, 8, 20, 21, 22, 30, 30, 34, 39, 40, 45, 45]\n",
      "Target sum: 61\n",
      "Found indices: i=14 (values[14]=21), j=20 (values[20]=40)\n",
      "#47 Loop:\n",
      "Values: [-40, -28, -27, -25, -20, -18, -11, -9, -8, -6, -5, 7, 11, 24, 26, 27, 27, 30, 35]\n",
      "Target sum: -31\n",
      "Found indices: i=3 (values[3]=-25), j=9 (values[9]=-6)\n",
      "#48 Loop:\n",
      "Values: [-47, -45, -43, -43, -38, -32, -31, -28, -17, -10, -2, -1, 11, 19, 23, 28, 28, 47]\n",
      "Target sum: 57\n",
      "Found indices: i=None , j=None \n",
      "#49 Loop:\n",
      "Values: [-48, -46, -43, -40, -36, -27, -26, -25, -24, -16, -13, -13, -10, -5, -4, -2, 0, 5, 9, 15, 18, 34, 38, 42, 44, 47, 48]\n",
      "Target sum: -56\n",
      "Found indices: i=1 (values[1]=-46), j=12 (values[12]=-10)\n",
      "#50 Loop:\n",
      "Values: [-44, -43, -42, -4, 0, 9, 10, 21, 28, 31, 40]\n",
      "Target sum: -59\n",
      "Found indices: i=None , j=None \n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "reps = 50\n",
    "for k in range(reps):\n",
    "    values = sorted(random.randint(-50, 50) for _ in range(random.randint(10, 30)))\n",
    "    target_sum = random.randint(-100, 100)\n",
    "    i, j = find_indices(values, target_sum)\n",
    "    print(f'#{k+1} Loop:')\n",
    "    print('Values:', values)\n",
    "    print('Target sum:', target_sum)\n",
    "    val_i = f\"(values[{i}]={values[i]})\" if i is not None else ''\n",
    "    val_j = f\"(values[{j}]={values[j]})\" if j is not None else ''\n",
    "    print(f'Found indices: i={i} {val_i}, j={j} {val_j}')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}